package primary.code07_Greedy;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 贪心算法题，举例几种贪心策略，并通过举反例和对数器的方式进行验证，不建议考试场合进行证明
 *
 * 只有一个会议室，多个会议开始结束时间不同，会议之间的时间不能有冲突
 * 如何安排会议，使得一天中会议室能够安排的数量最多
 *
 * 思路：
 * 优先安排结束时间最早的会议
 *
 */
public class Code01_ArrangeMeeting {

    public static int maxMeetingCount(int[][] meetings) {
        int count = 0;
        int last = 0;
        //按照结束时间进行排序
        Arrays.sort(meetings, ((o1, o2) -> o1[1] - o2[1]));
        for (int[] meeting : meetings) {
            if (meeting[0] >= last) {
                count++;
                last = meeting[1];
            }
        }
        return count;
    }

    public static int maxMeetingCountTest(int[][] meetings) {
        Arrays.sort(meetings, (m1, m2) -> m1[1] - m2[1]);
        int count = 0;
        int lastTimeLine = 0;
        for (int[] meeting : meetings) {
            if (meeting[0] >=lastTimeLine) {
                count++;
                lastTimeLine = meeting[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] meetings = {
                {1, 3},
                {2, 4},
                {5, 10},
                {7, 18},
                {5, 23},
                {12, 20},
                {18, 24},
                {15, 20}
        };
        int res1 = maxMeetingCount(meetings);
        int res2 = maxMeetingCountTest(meetings);
        System.out.println("最多可以安排的会议数量:" + res1);
        System.out.println("最多可以安排的会议数量:" + res2);
    }
}
